

/*
10/31
238. 除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pro(n), f(n + 1), g(n + 1);
        f[0] = g[n - 1] = 1;
        for (int i = 1; i < f.size(); ++i)
            f[i] = f[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; --i)
            g[i] = g[i + 1] * nums[i + 1];

        for (int i = 0; i < n; ++i)
        {
            pro[i] = f[i] * g[i];
        }
        return pro;
    }
};

724. 寻找数组的中心下标
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        for (int i = 1; i < f.size(); ++i)
            f[i] = f[i - 1] + nums[i - 1];
        for (int i = n - 2; i >= 0; --i)
            g[i] = g[i + 1] + nums[i + 1];

        for (int i = 0; i < n; ++i)
        {
            if (f[i] == g[i])
                return i;
        }
        return -1;
    }
};

DP35 【模板】二维前缀和
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> nums(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> nums[i][j];

    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for (int i = 1; i < n + 1; ++i)
        for (int j = 1; j < m + 1; ++j)
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + nums[i][j];

    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    while (q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 -1] << endl;
    }
    return 0;
}

10/30
DP34 【模板】前缀和
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, q = 0;
    cin >> n >> q;

    vector<int> arr(n + 1);
    for (int i = 1; i < n + 1; ++i)
        cin >> arr[i];

    vector<long long> dp(n + 1);
    for (int i = 1; i < n + 1; ++i)
        dp[i] = arr[i] + dp[i - 1];

    while (q--)
    {
        int l = 0, r = 0;
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

LCR 173. 点名
class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0, right = records.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid)
                left = mid + 1;
            else
                right = mid;
        }
        return records[left] == left ? left + 1 : left;
    }
};

153. 寻找旋转排序数组中的最小值
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, x = nums[right];
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > x)
                left = mid + 1;
            else
                right = mid;
        }
        return nums[left];
    }
};


10/28
2351. 第一个出现两次的字母
class Solution {
public:
    char repeatedCharacter(string s) {
        int hash[26];
        for (int i = 0; i < s.size(); ++i)
        {
            hash[s[i] - 'a']++;
            if (hash[s[i] - 'a'] == 2)
                return s[i];
        }
        return ' ';
    }
};

LCR 179. 查找总价格为目标值的两个商品
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        for (int left = 0, right = price.size() - 1; left < right; )
        {
            int sum = price[left] + price[right];
            if (sum > target)
                --right;
            else if (sum < target)
                ++left;
            else
                return {price[left], price[right]};
        }
        return {0, 0};
    }
};

162. 寻找峰值
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] >= nums[mid - 1])
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};

852. 山脉数组的峰顶索引
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] >= arr[mid - 1])
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};

10/27
35. 搜索插入位置
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        if (nums[left] < target)
            return nums.size();
        return left;
    }
};

BM5 合并k个已排序的链表
class Solution {
public:
    ListNode* merge(ListNode* pHead1, ListNode* pHead2)
    {
        if (pHead1 == nullptr)
            return pHead2;
        if (pHead2 == nullptr)
            return pHead1;
        ListNode* pHead = new ListNode(0), *head = pHead;
        while (pHead1 && pHead2)
        {
            if (pHead1->val <= pHead2->val)
            {
                head->next = pHead1;
                pHead1 = pHead1->next;
            }
            else
            {
                head->next = pHead2;
                pHead2 = pHead2->next;
            }
            head = head->next;
        }
        if (pHead1)
            head->next = pHead1;
        else
            head->next = pHead2;

        return pHead->next;
    }

    ListNode* divideMerge(vector<ListNode*>& lists, int left, int right)
    {
        if (left > right)
            return nullptr;
        else if (left == right)
            return lists[left];
        int mid = left + (right - left) / 2;
        return merge(divideMerge(lists, left, mid),
            divideMerge(lists, mid + 1, right));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return divideMerge(lists, 0, lists.size() - 1);
    }
};

BM4 合并两个排序的链表
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* pHead = new ListNode(0), *head = pHead;
        while (pHead1 && pHead2)
        {
            if (pHead1->val <= pHead2->val)
            {
                head->next = pHead1;
                pHead1 = pHead1->next;
            }
            else
            {
                head->next = pHead2;
                pHead2 = pHead2->next;
            }
            head = head->next;
        }
        if (pHead1)
            head->next = pHead1;
        else
            head->next = pHead2;
        return pHead->next;
    }
};

10/26
BM2 链表内指定区间反转
class Solution {
public:
    vector<ListNode*> reserve(ListNode* head)
    {
        if (head == nullptr)
            return {nullptr};
        ListNode *prev = nullptr, *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur, cur = next;
        }
        return {prev, head};
    }


    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n)
            return head;
        ListNode* pHead = new ListNode(0), *prev = pHead, *cur = pHead;
        ListNode* head1 = nullptr, *head2 = nullptr, *head3 = nullptr,
            *head4 = nullptr;
        pHead->next = head;
        while (cur)
        {
            ListNode* next = cur->next;
            if (m == 0)
            {
                cout << prev->val << endl;
                head1 = prev, head1->next = nullptr;
                head2 = cur;
            }
            if (n == 0)
            {
                head3 = cur;
                head4 = cur->next;
                head3->next = nullptr;
                break;
            }
            --m, --n;
            prev = cur, cur = next;
        }
        vector<ListNode*> vL = reserve(head2);
        head2 = vL[0];
        head3 = vL[1];
        head1->next = head2;
        head3->next = head4;
        return pHead->next;
    }
};

BM1 反转链表
class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        ListNode *prev = nullptr, *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur, cur = next;
        }
        return prev;
    }
};

10/25
#include <stdio.h>
int main()
{
    int year = 0, month = 0, day = 0;
    scanf("%d %d %d", &year, &month, &day);
    int flag = 0;
    if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
        flag = 1;
    switch (month)
    {
    case 1:
    case 3:
    case 5:
    case 7:
    case 8:
    case 10:
    case 12:
        day += 1;
        month += day / 32;
        day %= 32;
        year += month / 13;
        month %= 13;
        break;
    case 2:
    case 4:
    case 6:
    case 9:
    case 11:
        if (month == 2 && day == 29 && flag)
        {
            day = 1;
            month = 3;
            break;
        }
        else if (month == 2 && day == 28 && !flag)
        {
            day = 1;
            month = 3;
            break;
        }
        day += 1;
        month += day / 32;
        day %= 32;
        year += month / 13;
        month %= 13;
        break;
    }
    printf("%d %d %d", year, month, day);
    return 0;
}

10/22

704. 二分查找
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0)
            return {-1, -1};
        int begin = 0;
        // 二分查找左端点
        int left = 0, right = nums.size() -1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target)
                right = mid;
            else
                left = mid + 1;
        }
        if (nums[left] != target)
            return {-1, -1};
        begin = left;
        // 二分查找右端点
        right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target)
                left = mid;
            else
                right = mid - 1;
        }
        return {begin, right};
    }
};

69. x 的平方根
class Solution {
public:
    int mySqrt(int x) {
        if (x < 1)
            return 0;
        int left = 1, right = x;
        while (left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x)
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};

25. 【模板】一维前缀和（easy）
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> vi(n + 1);
    vector<long long> dp(n + 1);
    for (int i = 1; i < n + 1; ++i)
        cin >> vi[i];
    vi[0] = dp[0] = 0;
    for (int i = 1; i < n + 1; ++i)
        dp[i] = dp[i - 1] + vi[i];
    
    while (q--)
    {
        int l = 0, r = 0;
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}


DP35 【模板】二维前缀和
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> vi(n + 1, vector<int>(m + 1));
    for (int i = 1; i < n + 1; ++i)
        for (int j = 1; j < m + 1; ++j)
            cin >> vi[i][j];
    
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for (int i = 1; i < n + 1; ++i)
        for (int j = 1; j < m + 1; ++j)
            dp[i][j] =  dp[i - 1][j] + dp[i][j - 1] + vi[i][j] - dp[i - 1][j - 1];
    
    while (q--)
    {
        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}



724. 寻找数组的中心下标
class Solution 
{
public:
    int pivotIndex(vector<int>& nums) 
    {
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        for (int i = 1; i < dp.size(); ++i)
            dp[i] = dp[i - 1] + nums[i];
        
        for (int i = 0; i < dp.size(); ++i)
        {
            if (dp[dp.size() - 1] - dp[i] == dp[i] - nums[i])
                return i;
        }
        return -1;
    }
};

class Solution 
{
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> front(n), tail(n);

        for (int i = 1; i < n; ++i)
            front[i] = front[i - 1] + nums[i - 1];

        for (int i = n - 2; i >= 0; --i)
            tail[i] = tail[i + 1] + nums[i + 1];
        
        for (int i = 0; i < n; ++i)
        {
            if (front[i] == tail[i])
                return i;
        }
        return -1;
    }
};

238. 除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> front(n, 1), tail(n, 1), nnums(n);

        for (int i = 1; i < n; ++i)
            front[i] = front[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; --i)
            tail[i] = tail[i + 1] * nums[i + 1];

        for (int i = 0; i < n; ++i)
            nnums[i] = front[i] * tail[i];
        return nnums;
    }
};

560. 和为 K 的子数组
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1;

        int sum = 0, ret = 0;

        for (auto x : nums)
        {
            sum += x;
            if (hash.count(sum - k))
                ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};

974. 和可被 K 整除的子数组
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1;
        int sum = 0, ret = 0;
        for (auto x: nums)
        {  
            sum += x;
            int r = (sum % k + k) % k;
            if (hash.count(r))
                ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};

525. 连续数组
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        for (auto& x: nums)
        {
            if (x == 0)
                x = -1;
        }

        unordered_map<int, int> hash;
        hash[0] = -1;
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if (hash.count(sum))
                ret = max(ret, i - hash[sum]);
            else
                hash[sum] = i;
        }
        return ret;
    }
};

1314. 矩阵区域和
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        vector<vector<int>> answer(m, vector<int>(n));

        for (int i = 1; i < dp.size(); ++i)
            for (int j = 1; j < dp[0].size(); ++j)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
        
        for (int i = 0; i < answer.size(); ++i)
        {
            for (int j = 0; j < answer[0].size(); ++j)
            {
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
                 answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return answer;
    }
};

191. 位1的个数
class Solution {
public:
    int hammingWeight(int n) {
        int tamp = 0;
        while (n)
        {
            if (n & 1)
                tamp++;
            n = n >> 1;
        }
        return tamp;
    }
};


338. 比特位计数
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> vi(n + 1, 0);
        for (int i = 0; i < vi.size(); ++i)
        {
            int j = i;
            while (j)
            {
                if (j & 1) vi[i]++;
                j = j >> 1;
            }
        }
        return vi;
    }
};

461. 汉明距离
class Solution {
public:
    int hammingDistance(int x, int y) {
        int z = x ^ y, tamp = 0;
        while (z)
        {
            if (z & 1) tamp++;
            z = z >> 1;
        }
        return tamp;
    }
};


136. 只出现一次的数字
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int tmp = 0;
        for (int i = 0; i < nums.size(); ++i)
            tmp ^= nums[i];
        return tmp;
    }
};

面试题 01.01. 判定字符是否唯一
class Solution {
public:
    bool isUnique(string astr) {
        if (astr.size() > 26)
            return false;
        int hash = 0;
        for (auto x : astr)
        {
            if ((hash >> (x - 'a')) & 1)
                return false;
            else
                hash |= 1 << (x - 'a');
        }
        return true;
    }
};

268. 丢失的数字
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int tmp = 0;
        for (auto num : nums)
            tmp ^= num;
        
        for (int i = 0; i <= nums.size(); ++i)
            tmp ^= i;
        
        return tmp;
    }
};

371. 两整数之和
class Solution {
public:
    int getSum(int a, int b) {
        while (b)
        {
            int c = a ^ b;
            b = (a & b) << 1;
            a = c;
        }
        return a;
    }
};

137. 只出现一次的数字 II
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int tamp = 0;
        for (int i = 0; i < 32; ++i)
        {
            int sum = 0;
            for (auto num : nums)
            {
                if (((num >> i) & 1) == 1)
                    sum++;
            }
            sum %= 3;
            if (sum == 1)
                tamp |= (1 << i);
        }
        return tamp;
    }
};


面试题 17.19. 消失的两个数字
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tamp = 0;
        for (auto num : nums)
            tamp ^= num;
        for (int i = 1; i <= nums.size() + 2; ++i)
            tamp ^= i;
        
        int diff = 0;
        while (1)
        {
            if (((tamp >> diff) & 1) == 1)
                break;
            else
                diff++;
        }

        int a = 0, b = 0;
        for (auto num : nums)
        {
            if (((num >> diff) & 1) == 1)
                a ^= num;
            else   
                b ^= num;
        }

        for (int i = 1; i <= nums.size() + 2; ++i)
        {
            if (((i >> diff) & 1) == 1)
                a ^= i;
            else   
                b ^= i;
        }

        return {a, b};
    }
};

1576. 替换所有的问号
class Solution {
public:
    string modifyString(string s) {
        int n = s.size();
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == '?')
            {
                for (char ch = 'a'; ch <= 'z'; ch++)
                {
                    if ((i == 0 || ch != s[i - 1]) && (i ==  n - 1 || ch != s[i + 1]))
                    {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};
*/